#ifndef BFS_H_
#define BFS_H_

#include <algorithm>
#include <deque>
#include <list>
#include <queue>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>


namespace lxj
{
// 地图分析
// 你现在手里有一份大小为 n x n 的 网格 grid
// 上面的每个 单元格 都用 0 和 1 标记好了其中 0 代表海洋，1 代表陆地。
// 请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的
// 并返回该距离。如果网格上只有陆地或者海洋，请返回 -1。
// 我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：
// (x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。
// 测试链接 : https://leetcode.cn/problems/as-far-from-land-as-possible/
class AsFarFromLandAsPossible {
    inline constexpr static int MAXN                  = 101;
    inline static int           queue[MAXN * MAXN][2] = {};
    inline static int           l = 0, r = 0;

    inline static bool visited[MAXN][MAXN] = {};

    inline constexpr static int move[5] = {-1, 0, 1, 0, -1};

public:
    inline int maxDistance(std::vector<std::vector<int>>& grid)
    {
        l = 0, r = 0;
        int n = grid.size();
        int m = grid[0].size();

        int sea = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    queue[r][0]   = i;
                    queue[r++][1] = j;
                    visited[i][j] = true;
                }
                else {
                    visited[i][j] = false;
                    sea++;
                }
            }
        }
        if (sea == 0 || sea == n * m) return -1;

        int level = 0;
        while (l < r) {
            level++;
            int size = r - l;
            for (int k = 0, x, y, nx, ny; k < size; k++) {
                x = queue[l][0];
                y = queue[l++][1];
                for (int i = 0; i < 4; i++) {
                    nx = x + move[i];
                    ny = y + move[i + 1];
                    if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny]) {
                        visited[nx][ny] = true;
                        queue[r][0]     = nx;
                        queue[r++][1]   = ny;
                    }
                }
            }
        }

        return level - 1;
    }
};

// 贴纸拼词
// 我们有 n 种不同的贴纸。每个贴纸上都有一个小写的英文单词。
// 您想要拼写出给定的字符串 target ，方法是从收集的贴纸中切割单个字母并重新排列它们
// 如果你愿意，你可以多次使用每个贴纸，每个贴纸的数量是无限的。
// 返回你需要拼出 target 的最小贴纸数量。如果任务不可能，则返回 -1
// 注意：在所有的测试用例中，所有的单词都是从 1000 个最常见的美国英语单词中随机选择的
// 并且 target 被选择为两个随机单词的连接。
// 测试链接 : https://leetcode.cn/problems/stickers-to-spell-word/
class StickersToSpellWord {
    inline constexpr static int MAXN        = 401;
    inline static std::string   queue[MAXN] = {};
    inline static int           l = 0, r = 0;

    std::vector<std::vector<std::string>> graph;
    std::unordered_set<std::string>       visited;

    inline std::string next(const std::string& cur, const std::string& s)
    {
        std::string ns;
        for (int i = 0, j = 0; i < cur.size();) {
            if (j == s.size()) {
                ns += cur[i++];
            }
            else {
                if (cur[i] < s[j]) {
                    ns += cur[i++];
                }
                else if (cur[i] > s[j]) {
                    j++;
                }
                else {
                    i++;
                    j++;
                }
            }
        }
        return ns;
    }

public:
    inline int minStickers(std::vector<std::string>& stickers, std::string target)
    {
        int n = stickers.size();
        graph = std::vector<std::vector<std::string>>(26);
        for (int i = 0; i < n; i++) {
            std::sort(stickers[i].begin(), stickers[i].end());
            for (int j = 0; j < stickers[i].size(); j++) {
                if (j == 0 || stickers[i][j] != stickers[i][j - 1]) {
                    graph[stickers[i][j] - 'a'].push_back(stickers[i]);
                }
            }
        }

        visited = std::unordered_set<std::string>();
        std::sort(target.begin(), target.end());
        int level = 1;
        l = r      = 0;
        queue[r++] = target;
        while (l < r) {
            int size = r - l;
            for (int i = 0; i < size; i++) {
                std::string& cur = queue[l++];
                for (auto& s : graph[cur[0] - 'a']) {
                    std::string next = this->next(cur, s);
                    if (next == "") {
                        return level;
                    }
                    else if (visited.count(next) == 0) {
                        queue[r++] = next;
                        visited.insert(next);
                    }
                }
            }
            level++;
        }
        return -1;
    }
};

// 到达角落需要移除障碍物的最小数目
// 给你一个下标从 0 开始的二维整数数组 grid ，数组大小为 m x n
// 每个单元格都是两个值之一：
// 0 表示一个 空 单元格，
// 1 表示一个可以移除的 障碍物
// 你可以向上、下、左、右移动，从一个空单元格移动到另一个空单元格。
// 现在你需要从左上角 (0, 0) 移动到右下角 (m - 1, n - 1)
// 返回需要移除的障碍物的最小数目
// 测试链接 : https://leetcode.cn/problems/minimum-obstacle-removal-to-reach-corner/
inline int minimumObstacles(std::vector<std::vector<int>>& grid)
{
    constexpr int                 MAX = ~(1 << 31);
    int                           n   = grid.size();
    int                           m   = grid[0].size();
    std::vector<std::vector<int>> distance(n, std::vector<int>(m));
    for (auto& d : distance) {
        for (auto& i : d) i = MAX;
    }
    distance[0][0] = 0;

    int                              move[] = {-1, 0, 1, 0, -1};
    std::vector<std::pair<int, int>> deque(2 * n * m);
    int                              l = n * m, r = n * m;
    deque[r++] = {0, 0};
    while (l < r) {
        int x = deque[l].first;
        int y = deque[l++].second;
        if (x == n - 1 && y == m - 1) return distance[x][y];
        for (int i = 0; i < 4; i++) {
            int nx = x + move[i];
            int ny = y + move[i + 1];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m &&
                distance[x][y] + grid[nx][ny] < distance[nx][ny]) {
                distance[nx][ny] = distance[x][y] + grid[nx][ny];
                grid[nx][ny] == 0 ? deque[--l] = {nx, ny} : deque[r++] = {nx, ny};
            }
        }
    }

    return -1;
}

// 使网格图至少有一条有效路径的最小代价
// 给你一个 m * n 的网格图 grid 。 grid 中每个格子都有一个数字
// 对应着从该格子出发下一步走的方向。 grid[i][j] 中的数字可能为以下几种情况：
// 1 ，下一步往右走，也就是你会从 grid[i][j] 走到 grid[i][j + 1]
// 2 ，下一步往左走，也就是你会从 grid[i][j] 走到 grid[i][j - 1]
// 3 ，下一步往下走，也就是你会从 grid[i][j] 走到 grid[i + 1][j]
// 4 ，下一步往上走，也就是你会从 grid[i][j] 走到 grid[i - 1][j]
// 注意网格图中可能会有 无效数字 ，因为它们可能指向 grid 以外的区域
// 一开始，你会从最左上角的格子 (0,0) 出发
// 我们定义一条 有效路径 为从格子 (0,0) 出发，每一步都顺着数字对应方向走
// 最终在最右下角的格子 (m - 1, n - 1) 结束的路径
// 有效路径 不需要是最短路径
// 你可以花费1的代价修改一个格子中的数字，但每个格子中的数字 只能修改一次
// 请你返回让网格图至少有一条有效路径的最小代价
// 测试链接 : https://leetcode.cn/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/
inline int minCost(std::vector<std::vector<int>>& grid)
{
    constexpr int                 MAX = ~(1 << 31);
    int                           m   = grid.size();
    int                           n   = grid[0].size();
    std::vector<std::vector<int>> distance(m, std::vector<int>(n));
    for (auto& d : distance) {
        for (auto& i : d) i = MAX;
    }
    distance[0][0] = 0;

    int                             move[][2] = {{}, {0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    std::deque<std::pair<int, int>> deque;
    deque.push_back({0, 0});
    while (!deque.empty()) {
        auto cur = deque.front();
        int  x   = cur.first;
        int  y   = cur.second;
        deque.pop_front();
        if (x == m - 1 && y == n - 1) return distance[x][y];
        for (int i = 1; i <= 4; i++) {
            int nx     = x + move[i][0];
            int ny     = y + move[i][1];
            int weight = grid[x][y] == i ? 0 : 1;
            if (nx >= 0 && nx < m && ny >= 0 && ny < n &&
                distance[x][y] + weight < distance[nx][ny]) {
                distance[nx][ny] = distance[x][y] + weight;
                weight == 0 ? deque.push_front({nx, ny}) : deque.push_back({nx, ny});
            }
        }
    }
    return -1;
}

// 二维接雨水
// 给你一个 m * n 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度
// 请计算图中形状最多能接多少体积的雨水。
// 测试链接 : https://leetcode.cn/problems/trapping-rain-water-ii/
inline int trapRainWater(std::vector<std::vector<int>>& heightMap)
{
    int m = heightMap.size();
    int n = heightMap[0].size();
    struct node {
        int a, b, c;
    };
    auto my_comp = [](const node& x, const node& y) { return x.c > y.c; };
    std::priority_queue<node, std::vector<node>, decltype(my_comp)> heap(my_comp);
    std::vector<std::vector<bool>> visited(m, std::vector<bool>(n));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                heap.push({.a = i, .b = j, .c = heightMap[i][j]});
                visited[i][j] = true;
            }
            else {
                visited[i][j] = false;
            }
        }
    }

    int move[] = {-1, 0, 1, 0, -1};
    int ans    = 0;
    while (!heap.empty()) {
        auto& cur = heap.top();
        int   r   = cur.a;
        int   c   = cur.b;
        int   w   = cur.c;
        heap.pop();
        ans += w - heightMap[r][c];
        for (int i = 0, nr, nc; i < 4; i++) {
            nr = r + move[i];
            nc = c + move[i + 1];
            if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc]) {
                heap.push({.a = nr, .b = nc, .c = heightMap[nr][nc] > w ? heightMap[nr][nc] : w});
                visited[nr][nc] = true;
            }
        }
    }
    return ans;
}

// 单词接龙 II
// 按字典 wordList 完成从单词 beginWord 到单词 endWord 转化
// 一个表示此过程的 转换序列 是形式上像
// beginWord -> s1 -> s2 -> ... -> sk 这样的单词序列，并满足：
// 每对相邻的单词之间仅有单个字母不同
// 转换过程中的每个单词 si（1 <= i <= k）必须是字典 wordList 中的单词
// 注意，beginWord 不必是字典 wordList 中的单词
// sk == endWord
// 给你两个单词 beginWord 和 endWord ，以及一个字典 wordList
// 请你找出并返回所有从 beginWord 到 endWord 的 最短转换序列
// 如果不存在这样的转换序列，返回一个空列表
// 每个序列都应该以单词列表 [beginWord, s1, s2, ..., sk] 的形式返回
// 测试链接 : https://leetcode.cn/problems/word-ladder-ii/
class WordLadderII {
    inline static std::unordered_set<std::string> dict = std::unordered_set<std::string>();

    inline static std::unordered_set<std::string> curLevel  = std::unordered_set<std::string>();
    inline static std::unordered_set<std::string> nextLevel = std::unordered_set<std::string>();

    // 反向图
    inline static std::unordered_map<std::string, std::vector<std::string>> graph =
        std::unordered_map<std::string, std::vector<std::string>>();

    // 记录路径，当生成一条有效路的时候，拷贝进ans！
    inline static std::list<std::string>                path = std::list<std::string>();
    inline static std::vector<std::vector<std::string>> ans =
        std::vector<std::vector<std::string>>();

    inline void build(std::vector<std::string>& wordList)
    {
        dict.clear();
        graph.clear();
        path.clear();
        ans.clear();
        curLevel.clear();
        nextLevel.clear();
        for (auto& word : wordList) {
            dict.insert(word);
        }
    }

    // begin -> end ，一层层bfs去，建图
    // 返回值：真的能找到end，返回true；false
    inline bool bfs(std::string begin, std::string end)
    {
        bool find = false;
        curLevel.insert(begin);
        while (!curLevel.empty()) {
            // dict.erase(curLevel.begin(), curLevel.end());
            for (auto p = curLevel.begin(); p != curLevel.end(); p++) {
                dict.erase(*p);
            }
            for (std::string word : curLevel) {
                // word : 去扩
                // 每个位置，字符a~z，换一遍！检查在词表中是否存在
                // 避免，加工出自己
                std::string str = word;
                for (int i = 0; i < word.size(); i++) {
                    char old = str[i];
                    for (char ch = 'a'; ch <= 'z'; ch++) {
                        str[i] = ch;
                        if (dict.count(str) > 0 && str != word) {
                            find = str == end ? true : find;
                            graph[str].push_back(word);
                            nextLevel.insert(str);
                        }
                    }
                    str[i] = old;
                }
            }
            if (find) {
                return true;
            }
            else {
                std::unordered_set<std::string> tmp = curLevel;
                curLevel                            = nextLevel;
                nextLevel                           = tmp;
                nextLevel.clear();
            }
        }
        return false;
    }

    inline void dfs(const std::string& word, const std::string& aim)
    {
        path.push_front(word);
        if (word == aim) {
            ans.push_back(std::vector<std::string>(path.begin(), path.end()));
        }
        else if (graph.count(word) > 0) {
            for (const auto& next : graph[word]) dfs(next, aim);
        }
        path.pop_front();
    }

public:
    inline std::vector<std::vector<std::string>> findLadders(std::string               beginWord,
                                                             std::string               endWord,
                                                             std::vector<std::string>& wordList)
    {
        build(wordList);
        if (dict.count(endWord) == 0) return ans;
        if (bfs(beginWord, endWord)) dfs(endWord, beginWord);
        return ans;
    }
};
}   // namespace lxj

#endif